import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;

@SuppressWarnings("unchecked")
public class PyramidAlg {
	private ArrayList<Integer> DiffSet; //This variable should not be modified in any way!!!
	public ArrayList<Integer> OriginalSet;
	
	public PyramidAlg(ArrayList<Integer> ds) { //expecting sorted diff set
		DiffSet = ds;
		if (unsorted(ds)) {
			System.err.println("Unsorted set of differences!");
			Collections.sort(ds);
		}
		ArrayList<ArrayList<Integer>> ba = createBaseArray();
		System.out.println("Found "+ba.size()+" combinations");
		OriginalSet = getSet(ba, DiffSet);
		
	}
	
	private boolean unsorted(ArrayList<Integer> ds) {
		Iterator<Integer> it = ds.iterator();
		int v = it.next();
		while (it.hasNext()) {
			int suc = it.next(); //successor
			if (suc < v) {
				return true;
			}
			v = suc;
		}
		return false;
	}
	
	/*
	 * Returns list of every set that could when ordered constuct a Base 
	 */
	private ArrayList<ArrayList<Integer>> createBaseArray() { 
		int peak = DiffSet.get(DiffSet.size()-1);
		int foot = peak - DiffSet.get(DiffSet.size() - 2);
		int baseSize = (int)Math.floor(Math.sqrt(2*DiffSet.size()));
		if (!DiffSet.contains(foot)) {
			System.err.println("foot not in DS");
			return null;
		}
		ArrayList<Integer> mustBeInBase = getMustBeInBase(foot);
		
		if (mustBeInBase.size() > baseSize) {
			System.err.println("mustBeInBase > baseSize / "+mustBeInBase.size()+" > "+ baseSize);
			return null;
		} else  if (mustBeInBase.size() == baseSize) {
			ArrayList<ArrayList<Integer>> res = new  ArrayList<ArrayList<Integer>>();
			res.add(mustBeInBase);
			return res;	
		}
			//actual algorithm
		ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
		int diff = baseSize - mustBeInBase.size();
		int sum = peak - getSum(mustBeInBase);
		System.out.println("count:"+diff+", sum: "+sum+ ", size: "+baseSize);
		HashMap<Integer, Integer> fsf = new HashMap<>(); //freq. seq. of unused ints
		for (int i = 0; i< DiffSet.size(); i++) {
			int temp = DiffSet.get(i);
			int v = (fsf.get(temp) != null)?fsf.get(temp)+1:1;
			fsf.put(temp,v);
		}
		for (int i = 0; i < mustBeInBase.size(); i++) {
			int temp =DiffSet.get(i);
			fsf.put(temp,fsf.get(temp)-1);
		}
		LinkedList<PartialRes> list = new LinkedList<PartialRes>();
		int gmax = DiffSet.size() - baseSize;
		while (DiffSet.get(gmax) > sum) {
			gmax--;
		}
		boolean[] canBeInBaseMap = new boolean[DiffSet.size()];
		for (int i = 0; i < canBeInBaseMap.length; i++) {
			canBeInBaseMap[i] = getCanBeInBase(DiffSet.get(i), baseSize);
		}
 		for (int i = 0; i <= gmax; i++) {
			int temp = DiffSet.get(i);
			
			if (temp > sum ) {
				break;
			}
			
			if (fsf.get(temp) < 1) {
				continue;
			}
			
			HashMap<Integer, Integer> tfsf = (HashMap<Integer, Integer>) fsf.clone();
			ArrayList<Integer> tbase = (ArrayList<Integer>) mustBeInBase.clone();
			tbase.add(temp);
			tfsf.put(temp, tfsf.get(temp)-1);
			list.addFirst(new PartialRes(tbase, tfsf,i,gmax ));	
		}
		
		while (!list.isEmpty()) {
			PartialRes pr = list.pollFirst();
			if (pr.base.size() == baseSize) {
				res.add(pr.base);
			}
			int tsum = peak - pr.getSum();
			if (tsum < 0) {
				continue; 
			}
			int tmin = pr.min;
			int tmax = pr.max;
			for (int i = tmin; i <= tmax; i++) {
				int temp = DiffSet.get(i);
				if (temp > tsum ) {
					tmax = i;
					break;
				}
				if (pr.fsf.get(temp) <= 0) {
					continue;
				}
				
				HashMap<Integer, Integer>tfsf = (HashMap<Integer, Integer>) pr.fsf.clone();
				ArrayList<Integer> tbase = (ArrayList<Integer>) pr.base.clone();
				tfsf.put(temp, tfsf.get(temp)-1);
				tbase.add(temp);
				list.addFirst(new PartialRes(tbase, tfsf,i+1,tmax));
			}
		}
		
		return res;
	}
	
	/*
	 * returns List of elements of DiffSet which are known to be in Base
	 */
	public ArrayList<Integer> getMustBeInBase(int foot) {
		ArrayList<Integer> res = new ArrayList<Integer>();
		for (int i = 0; i < DiffSet.size(); i++) {
			if (!canBeMade(DiffSet.get(i), DiffSet)) {
				res.add(DiffSet.get(i));
			}
		}
		System.out.print("Must be in base: ");
		for (Object o:res.toArray()) {
			System.out.print((int)o+", ");
		} 
		System.out.println();
		if (!res.contains(foot)) {
			res.add(foot);
		}
		return res;
	}
	
	public boolean getCanBeInBase(int n, int baseSize) {
		if (DiffSet.indexOf(n) == -1) {
			System.err.println(n+" not in DiffSet");
			return false;
		}
		int max = DiffSet.get(DiffSet.size()-1);
		int counter = 0;
		for (int i = 0; i < DiffSet.size(); i++) {
			if (DiffSet.indexOf(DiffSet.get(i)+n) > -1) {
				//if n + DiffSet[i] is in DiffSet
				counter++;
				if (counter >= (baseSize -1)) {
					return true;
				}
				if (DiffSet.get(i)+n > max) {
					return counter >= (baseSize -1);
				}
			}
		}
		return false;
	}
	
	
	

	public ArrayList<Integer> getSet(ArrayList<ArrayList<Integer>> arrays, ArrayList<Integer> DiffSet) {
		
		int foot = DiffSet.get(DiffSet.size() -1) - DiffSet.get(DiffSet.size()-2);
		//foot is always same
		
		HashMap<Integer, Integer> freqSeq = arrayToFreqSeq(DiffSet);
		freqSeq.put(foot, freqSeq.get(foot)-1);
		for (int i = 0; i < arrays.size(); i++) {
			ArrayList<Integer> ar = arrays.get(i);
			ArrayList<Integer> added = new ArrayList<>();
			added.add(foot);
			HashMap<Integer, Integer> nonadded = arrayToFreqSeq(ar);
			nonadded.put(foot, nonadded.get(foot)-1);
			LinkedList<CheckRes> list = new LinkedList<>();
			for (int j = 0; j < nonadded.size(); j++) {
				if (freqSeq.get(foot + j) > 0) {
					if (nonadded.get(j) < 1) {
						continue;
					} 
					
					ArrayList<Integer> a = (ArrayList<Integer>) added.clone();
					HashMap<Integer, Integer> n = (HashMap<Integer, Integer>) nonadded.clone();
					HashMap<Integer, Integer> f = (HashMap<Integer, Integer>) freqSeq.clone();
					
					a.add(j);
					n.put(j, nonadded.get(j)-1);
					f.put(foot+j, f.get(foot+j)-1);
					f.put(j,f.get(j)-1);
					list.addFirst(new CheckRes(a, n, f));
				}
			}
			
			while (!list.isEmpty()) { //trying depth-first search
				CheckRes c = list.pollFirst();
				if (c.added.size() == ar.size()) {
					if (finalTest(c.added, c.freqSeq)) {
						return c.added;
					} else {
						continue;
					}
				}
				for (int j = 0; j < c.nonadded.size(); j++) {
					if (c.nonadded.get(j) < 1) {
						continue; //filters results that weren't in tested set in first place
					}
					if (c.freqSeq.get(j) < 1) {
						break;//filters results where sum of partial result is equal to one of nonadded ints
					}
					
					HashMap<Integer, Integer> f = (HashMap<Integer, Integer>) c.freqSeq.clone();
					f.put(j, f.get(j)-1);
					boolean conflict = false; // if partial result is all right but not if j is next
					for (int k = 0; k < c.added.size(); k++) {
							int temp = f.get(c.getSumfrom(k)+ j);
							if ( temp <= 0) {
								conflict = true; 
								
							} else {
								f.put((c.getSumfrom(k))+ j,temp-1);
							}
						
					}
					if (conflict) {
						continue;
					}
						
						
					ArrayList<Integer> a = (ArrayList<Integer>) c.added.clone();
					HashMap<Integer, Integer> n = (HashMap<Integer, Integer>) c.nonadded.clone();
					
					a.add(j);
					n.put(j, n.get(j)-1);
					list.addFirst(new CheckRes(a, n, f));
					
				}
			}
		}
		System.out.println("No acceptable result found!");
		return null;
	}
	
	private HashMap<Integer, Integer> arrayToFreqSeq(ArrayList<Integer> array) {
		HashMap<Integer, Integer> res = new HashMap<>();
		int max =  array.get(array.size()-1);
		for (int i = 0; i <= max; i++) {
			res.put(i, 0);
		}
		for (int i = 0; i < array.size(); i++) {
			int key = array.get(i);
			res.put(key, res.get(key)+1);
		}
		return res;
	}
	
	
	private boolean finalTest(ArrayList<Integer> a, HashMap<Integer, Integer> f) { 
		for (int i = 0; i < a.size(); i++) {
			System.out.print(a.get(i)+" ");
		}
		boolean res = true;
		System.out.println();
		for (Integer n :f.keySet()) {
			if (f.get(n) != 0 ) {
				System.out.println("!!!"+n+" "+f.get(n));
				res = false;
			}
		}
		
		return res;
	}
	
	private int getSum(ArrayList<Integer> al) {
		int res = 0;
		Iterator<Integer> it = al.iterator();
		while (it.hasNext()) {
			res += it.next();
		}
		return res;
	}
	
	private boolean isSorted(ArrayList<Integer> list) {
		for (int i = 1; i < list.size();i++) {
			if (list.get(i-1)>list.get(i)) {
				return false;
			}
		}
		return true;
	}
	
	private boolean canBeMade(int n, ArrayList<Integer> base) { // returns if n can be made by addition from bases
		if (!isSorted(base)) {
			System.err.println("Unsorted list in  canBeMade!");
		}
		HashSet<Integer> set = new HashSet<Integer>();
		for (Object o: base.toArray()) {
			int temp = (int) o;
			if (temp < n) {
				for (Object p :set.toArray()) {
					if ((int)p+temp < n) {
						set.add((int)p+temp);
					} else if ((int)p+temp == n) {
						return true;
					}
				}	
				set.add(temp);
			} 
		}		
		return false;
	}
	
	private class CheckRes {
		ArrayList<Integer> added;
		HashMap<Integer, Integer> nonadded;
		HashMap<Integer, Integer> freqSeq;
		
		CheckRes(ArrayList<Integer> added, HashMap<Integer, Integer> nonadded,
				HashMap<Integer, Integer> freqSeq) {
			this.added = added;
			this.nonadded = nonadded;
			this.freqSeq = freqSeq;
		}
		
		int getSumfrom(int from) {
			int res = 0;
			for (int i = from; i < added.size(); i++) {
				res += added.get(i);
			}
			return res;
		}
	}
	
	
	private class PartialRes {
		ArrayList<Integer> base;
		HashMap<Integer, Integer> fsf;
		int min,max;
		PartialRes(ArrayList<Integer> base,HashMap<Integer, Integer> fsf , int min ,int max) {
			this.base = base;
			this.fsf = fsf;
			this.min = min;
			this.max = max;
		}
		
		int getSum() {
			int res = 0;
			for (int i = 0; i < base.size(); i++) {
				res += base.get(i);
			}
			return res;
		}
	}

}
